package com.kevinkk.backtracking;

import java.util.ArrayList;
import java.util.List;

/**
 * 给你一个字符串 s，请你将 s 分割成一些子串，使每个子串都是回文串
 * 返回 s 所有可能的分割方案。
 */

public class PalindromePartitioning {
    class Solution {
        List<List<String>> res = new ArrayList<>();
        List<String> path = new ArrayList<>();

        public List<List<String>> partition(String s) {
            backtracking(s, 0);
            return res;
        }

        private void backtracking(String s, int index){
            if(index == s.length()){
                res.add(new ArrayList<>(path));
                return;
            }

            for(int i = index; i < s.length(); i++){
                if(check(s, index, i)){
                    path.add(s.substring(index, i+1));
                    backtracking(s, i+1);
                    path.remove(path.size()-1);
                }
            }
        }

        private boolean check(String s, int l, int r){
            while(l < r){
                if(s.charAt(l) != s.charAt(r))
                    return false;
                l ++;
                r --;
            }

            return true;
        }
    }
}
